package leetcode_500;

import helpclass.TreeNode;

/**
 *@author 周杨
 *SerializeAndDeserializeBST_449 将一颗二叉搜索树序列化为字符串 再将其反序列化为一棵树
 *describe:用递归 利用队列的思想  每次从队列中找出左子树和右子树 其中返回的序列化是先序遍历得出的  AC 94%
 *2018年8月22日 下午12:20:05
 */
public class SerializeAndDeserializeBST_449 {
	
	public static void main(String[] args) {
		TreeNode root=new TreeNode(5);
		root.left=new TreeNode(3);
		root.left.right=new TreeNode(4);
		root.right=new TreeNode(7);
		
		SerializeAndDeserializeBST_449 test=new SerializeAndDeserializeBST_449();
		System.out.println(test.serialize(root));
	}
	
	 // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)
        	return null;
        StringBuilder sb=new StringBuilder();
        pre(root,sb);
        sb.deleteCharAt(sb.length()-1);//删除最后一个多余的#
        return sb.toString();
    }
    
    public void pre(TreeNode root,StringBuilder res) {
    	res.append(root.val).append("#");
    	if(root.left!=null)
    		pre(root.left,res);
    	if(root.right!=null)
    		pre(root.right,res);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
    	if(data==null)
    		return null;
    	String [] strs=data.split("#");
    	return help(strs,0,strs.length-1);
    }
    
    public TreeNode help(String strs[],int left,int right) {
    	if(left>right)
    		return null;
    	int now=Integer.parseInt(strs[left]);
    	TreeNode root=new TreeNode(now);
    	int mid=left+1;
    	while(mid<=right) {
    		if(Integer.parseInt(strs[mid])>now)
    			break;
    		++mid;
    	}
    	root.left=help(strs,left+1,mid-1);
    	root.right=help(strs,mid,right);
    	return root;
    }
}
